package problems.practice;

/**
 * 1870. 准时到达的列车最小时速
 * <p>https://leetcode.cn/problems/minimum-speed-to-arrive-on-time/</p>
 *
 * @author habitplus
 * @since 21:39, 2022/10/1
 */
public class T1870 {
    // 二分法
    public int minSpeedOnTime(int[] dist, double hour) {
        int n = dist.length;
        // 将小数转化成整数
        long h = Math.round(hour * 100);

        // 每一站加上等待时间至少为 1 小时，最后一战无等待时间
        if (h - (n - 1) * 100L <= 0) return -1;

        // 对速度进行二分枚举
        int l = 1;
        int r = (int) 1e7;
        int m;
        long t;
        while (l < r) {
            m = l + (r - l) / 2;
            t = 0;
            // 计算前 n - 1 个站的耗时
            for (int i = 0; i < n - 1; ++i) {
                // 取大于 dist[i]/m 的 最小整数
                t += (dist[i] - 1) / m + 1;
            }

            // 分式转化比较
            t = t * m + dist[n - 1];
            if (t * 100 <= h * m) {
                r = m;
            } else {
                l = m + 1;
            }
        }

        return l;
    }

    public static void main(String[] args) {
        double d = 2.01;
        System.out.println("d * 100 = " + (d * 100)); // 200.99999999999997
        System.out.println("(long) (d * 100) = " + (long) (d * 100)); // 200
        System.out.println("Math.round(d * 100) = " + Math.round(d * 100)); // 201

        d = 88.88;
        System.out.println("Math.round(d) = " + Math.round(d)); // 89

        d = 88.48;
        System.out.println("Math.round(d) = " + Math.round(d)); // 88


    }
}
